import java.util.ArrayList;
import java.util.List;

/**
* @description: 655. 输出二叉树
* @author hewei
* @date 2022/8/22 14:15
* @version 1.0
*/

public class PrintTree {

    List<List<String>> ans;
    int h;
    public List<List<String>> printTree(TreeNode root) {
        int m = process(root);
        int n = (int) (Math.pow(2, m) - 1);
        h = m - 1;
        ans = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            ans.add(new ArrayList<>());
            for (int j = 0; j < n; j++) {
                ans.get(i).add("");
            }
        }
        ans.get(0).set(n / 2, String.valueOf(root.val));
        dfs(root, 0, n / 2);
        return ans;
    }

    public void dfs(TreeNode node, int m, int n) {
        if (node == null || (node.left == null && node.right == null)) return;
        int x = m + 1;
        int y;
        if (node.left != null) {
            y = (int) (n - Math.pow(2, h - m - 1));
            ans.get(m + 1).set(y, String.valueOf(node.left.val));
            dfs(node.left, x, y);
        }
        if (node.right != null) {
            y = (int) (n + Math.pow(2, h - m - 1));
            ans.get(m + 1).set(y, String.valueOf(node.right.val));
            dfs(node.right, x, y);
        }
    }

    public int process(TreeNode node) {
        if (node == null) return 0;
        return Math.max(process(node.left), process(node.right)) + 1;
    }
}
